package queue;

import java.util.*;
import java.util.PriorityQueue;

//给出指定M个元素，取出其中前N的元素
public class Solution {


    /**
     * step1：取出所有的元素，并计算频次，放入TreeMap中
     * step2：自定义一个 Frequent 类，用来作为优先队列中的元素
     * step3：如果优先队列的底层使用的是最大堆，那么需要定义频次大在堆顶，还是频次小的在堆定
     * setp4：
     * @param nums：给定的数组
     * @param k：指定个数
     * @return
     */
    public List<Integer> topKFrequent(int[] nums,int k){
        //key：元素，value：频次
        TreeMap<Integer,Integer> map = new TreeMap<Integer, Integer>();
        for(int num : nums){
            if(map.containsKey(num)){
                //频次+1
                map.put(num,map.get(num) + 1);
            }else {
                //元素不存在，将元素放入map中
                map.put(num, 1);
            }
        }


        //优先队列
        PriorityQueue<Frequent> pq = new PriorityQueue<Frequent>( (o1, o2) -> o1.freq - o2.freq );
        for(int key : map.keySet()){
            //pg.getSize() < k ：还没有找完，继续找，也就是继续往优先队列中丢数据
            if(pq.size() < k){
                //入队
                pq.add(new Frequent(key,map.get(key)));
            }else if(map.get(key) > pq.peek().freq){
                //map.get(key) > pq.getFront().freq：即将插入的元素比优先队列头元素的频次还要大，那么需要将队列头出队，然后再将当前元素入队
                pq.remove();   //出队
                pq.add(new Frequent(key,map.get(key))); //入队
            }
        }

        LinkedList<Integer> res = new LinkedList<Integer>();
        while (!pq.isEmpty()){
            res.add(pq.remove().e);
        }

        return res;


    }


    private class Frequent implements Comparable<Frequent>{
        int e;      //元素
        int freq;   //频次

        public Frequent(int e , int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Frequent another) {
            //使用java的优先队列，底层实现是最小堆（就是根节点元素最小，然后依次排列）
            if(this.freq < another.freq){
                return -1;
            }
            if(this.freq > another.freq){
                return 1;
            }

            return 0;
        }
    }

}
